
public class Tp2_Ej3_Main {

	public static void main(String[] args) {
		String nombreArchivo = "Tp2";
		
		String archivoEntrada = ".\\resources\\" + nombreArchivo + "Ej3.in";
		String archivoSalida = ".\\resources\\" + nombreArchivo + "Ej3.out";
		String archivoTiempos = ".\\resources\\" + nombreArchivo + "Ej3.time";
		
		algoritmo(archivoEntrada, archivoSalida, archivoTiempos);
		
	}
	
	private static void algoritmo(String archivoEntrada, String archivoSalida, String archivoTiempos) {
		FileParser fp = new FileParser(archivoEntrada);
		FileWriter fw = new FileWriter(archivoSalida);
		FileWriter fwTiempos = new FileWriter(archivoTiempos);
		
		//mejorCaso(archivoEntrada);
		int cantidadRepeticiones=10;
		long minMedicion=9999999;
		boolean res = true;
		
		while (!fp.getLine().trim().equals("-1 -1 -1")) {
			Prision instancia = parsearInstancia(fp);
			for (int rep=0 ;rep<cantidadRepeticiones;rep++) {
				long tiempoInicio = System.nanoTime();
				res = sePuedeEscapar(instancia);
				long totalTiempo = System.nanoTime()- tiempoInicio;
				if (minMedicion>totalTiempo){
					minMedicion=totalTiempo;
				}
			}
			fwTiempos.writeLine(instancia.getCantHabitaciones() + " " + String.valueOf(minMedicion));
			minMedicion=9999999;
			System.out.println("El resultado de la instancia es: " + res);
			
			if (res)
				fw.writeLine("libre");
			else
				fw.writeLine("no");
		}
		
		fw.closeFile();
		fp.closeFile();
		fwTiempos.closeFile();
	}
	
	private static Prision parsearInstancia(FileParser fp) {
		String[] str = fp.getLine().trim().replaceAll("\\s+", " ").split("\\s");
		fp.nextLine();
		int cantHabitaciones = Integer.valueOf(str[0]);
		int cantPuertas = Integer.valueOf(str[1]);
		int cantPasillos = Integer.valueOf(str[2]);
		
		int puertas[] = new int[cantHabitaciones];
		int llaves[] = new int[cantHabitaciones];
		
		for (int i=0; i<cantHabitaciones; i++)
			puertas[i] = 0;
		
		for (int i=0; i<cantHabitaciones; i++)
			llaves[i] = 0;
		
		int i=0;
		while (i < cantPuertas) {
			str = fp.getLine().trim().replaceAll("\\s+", " ").split("\\s");
			fp.nextLine();
			int puerta = Integer.parseInt(str[0]);
			int habitacionDeLlave = Integer.parseInt(str[1]);
			int indice = puerta - 1;
			puertas[indice] = 1;
			indice = habitacionDeLlave - 1;
			llaves[indice] = puerta;
			i++;
		}
		
		Prision p = new Prision(cantHabitaciones);
		i = 0;
		while (i < cantPasillos) {
			str = fp.getLine().trim().replaceAll("\\s+", " ").split("\\s");
			fp.nextLine();
			p.agregarPasillo(Integer.parseInt(str[0])-1, Integer.parseInt(str[1])-1);
			i++;
		}
		
		for (int j=0; j<cantHabitaciones; j++) {
			Habitacion habitacion = new Habitacion();
			
			int et = j + 1;
			String etiqueta = String.valueOf(et);
			habitacion.setEtiqueta(etiqueta);
			
			boolean esPuerta;
			if (puertas[j] == 1)
				esPuerta = true;
			else
				esPuerta = false;
			habitacion.setEsPuerta(esPuerta);
			
			habitacion.setLlave(llaves[j]);
			
			p.agregarHabitacion(habitacion);
		}
		
		return p;
	}
	
	private static void peorCaso(String archivoSalida){
		FileWriter fw = new FileWriter(archivoSalida);
		String cadena="";
		for (int numMatriz=9;numMatriz<1000;numMatriz+=2 ){
			int matriz[][]=new int[numMatriz][numMatriz];
			cadena=String.valueOf(numMatriz)+" 0 "+ String.valueOf(numMatriz - 1);
			fw.writeLine(cadena);
			cadena="";

			
			for (int i=0;i<numMatriz - 1;i++){
				cadena+= " "+ String.valueOf(i+1) + " " + String.valueOf(i+2) ;
				fw.writeLine(cadena);
				cadena="";
			}
			
		}
		fw.writeLine("-1 -1 -1");
		fw.closeFile();
		
	}

	
	private static void mejorCaso(String archivoSalida){
		FileWriter fw = new FileWriter(archivoSalida);
		String cadena="";
		for (int numMatriz=9;numMatriz<1000;numMatriz+=2 ){
			int matriz[][]=new int[numMatriz][numMatriz];
			cadena=String.valueOf(numMatriz)+" 0 "+ String.valueOf(numMatriz);
			fw.writeLine(cadena);
			cadena="";

			
			for (int i=0;i<numMatriz - 1;i++){
				cadena+= " "+ String.valueOf(i+1) + " " + String.valueOf(i+2) ;
				fw.writeLine(cadena);
				cadena="";
			}
			cadena=" 1 "+String.valueOf(numMatriz);
			fw.writeLine(cadena);
			cadena="";
			
		}
		fw.writeLine("-1 -1 -1");
		fw.closeFile();
		
	}
	
	
	
	private static boolean sePuedeEscapar(Prision p) {
		int llaves[] = new int[p.getCantHabitaciones()];
		int puertas[] = new int[p.getCantHabitaciones()];
		
		boolean res = false;
		
		res = bfs(p, llaves, puertas);
		
		return res;
	}
	
	private static boolean bfs(Prision p, int llaves[], int puertas[]) {
		int listaVisitadosConBfs[] = new int[p.getCantHabitaciones()];
		Cola laCola = new Cola(p.getCantHabitaciones());
		boolean meEscape = false;
		
		// Comenzamos en el primer vertice.
		listaVisitadosConBfs[0] = 1;
		laCola.push(0);
		
		while(!laCola.vacio() && !meEscape) {
			// Tomamos un vertice no visitado adyacente al primero de la cola.
			int v = getVerticesNoVisitados(p, laCola.peek(), listaVisitadosConBfs);
			
			if(v == -1) { // Si no hay tal vertice.
				laCola.pop(); // Lo desencolamos.
			} else {
				if (v == p.getCantHabitaciones()-1) {
					meEscape = true;
				} else {
					listaVisitadosConBfs[v] = 1; // Lo marcamos como visitado.
					
					if (p.getListaHabitacion()[v].isEsPuerta()) { // Si es puerta.
						if (llaves[v] == 1){ // Si tengo la llave.
							laCola.push(v);
						} else { // Si no tengo la llave.
							puertas[v] = 1; // Lo agrego al arreglo de las puertas.
						}
					} else { //Si no es puerta
						if (p.getListaHabitacion()[v].getLlave() != 0) { // Si es llave.
							if (llaves[p.getListaHabitacion()[v].getLlave()-1] == 1) { // Si ya la tengo.
								laCola.push(v);
							} else { // Si no la tengo.
								if (puertas[p.getListaHabitacion()[v].getLlave()- 1] == 1) { // Si tengo la puerta en el arreglo.
									llaves[p.getListaHabitacion()[v].getLlave()-1] = 1;
									laCola.push(v);
									laCola.push(p.getListaHabitacion()[v].getLlave()-1);
								} else { // Si no tengo la puerta en el arreglo. 
									llaves[p.getListaHabitacion()[v].getLlave()-1] = 1;
									laCola.push(v);
								}
							}
						} else { // Si no es llave.
							laCola.push(v);
						}
					}
				}
			}
		}
		
		return meEscape;
	}
	
	private static int getVerticesNoVisitados(Prision p, int v, int[] listaVisitadosConBfs) {
		for(int j=0; j<p.getCantHabitaciones(); j++) {
			if(p.estaRelacionado(v, j) && listaVisitadosConBfs[j]==0)
				return j;
		}
		
		return -1;
	}
	
}
